/*
*	BFS广度优先遍历系列
*/

/*宽搜 一层一层遍历 每一层就是路径步数*/
/*多个起点开始搜索 不需要按层计数 遍历完所有节点就宽搜完成*/

/* ======================================================= FloodFill-BFS系列 =============================================================  */

//图形渲染-bfs
//https://leetcode.cn/problems/flood-fill/description/
class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        int prev = image[sr][sc];
        if(prev == color) return image;
        int m = image.size(),n=image[0].size();
        int dx[] = {0,0,1,-1},dy[] = {1,-1,0,0};

        queue<pair<int,int>> pq;
        pq.push({sr,sc});
        while(!pq.empty())
        {
            pair<int,int> tmp = pq.front();
            pq.pop();
            image[tmp.first][tmp.second]=color;
            for(int i = 0;i<4;++i)
            {
                int x = tmp.first+dx[i],y = tmp.second+dy[i];
                if(x>=0&&x<m&&y>=0&&y<n&&image[x][y]==prev) pq.push({x,y});
            }
        }
        return image;
    }
};



//岛屿数量-BFS
//https://leetcode.cn/problems/number-of-islands/submissions/
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<bool>> visit(m, vector<bool>(n, true));
        int dx[] = { 0,0,1,-1 }, dy[] = { 1,-1,0,0 };

        int ret = 0;
        queue<pair<int, int>> pq;
        for (int i = 0; i < m; ++i)
        {
            for (int k = 0; k < n; ++k)
            {
                if (grid[i][k] == '1' && visit[i][k])
                {
                    ++ret;
                    pq.push({ i,k });
                    while (!pq.empty())
                    {
                        pair<int, int> tmp = pq.front();
                        pq.pop();
                        visit[tmp.first][tmp.second] = false;
                        for (int j = 0; j < 4; ++j)
                        {
                            int x = tmp.first + dx[j], y = tmp.second + dy[j];
                            if (x >= 0 && x < m && y >= 0 && y < n && visit[x][y] && grid[x][y] == '1')
                            {
                                pq.push({ x,y });
                                visit[x][y] = false;
                            }
                        }
                    }

                }
            }
        }
        return ret;
    }
};
//无检测数组版
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size(),n = grid[0].size();
        int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0};
        queue<pair<int,int>> q;
        int ret = 0;
        for(int i = 0;i<m;++i)
        {
            for(int k = 0;k<n;++k)
            {
                if(grid[i][k] == '1')
                {
                    ++ret;
                    q.push({i,k});
                    grid[i][k] = '0';
                    while(!q.empty())
                    {
                        auto [x,y] = q.front(); q.pop();
                        for(int j = 0;j<4;++j)
                        {
                            int px = x+dx[j],py = y+dy[j];
                            if(px >= 0 && px < m && py >= 0 && py < n && grid[px][py]=='1') 
                            {
                                q.push({px,py});
                                grid[px][py] = '0';
                            }
                        }
                    }
                }
            }
        }
        return ret;
    }
};



//岛屿的最大面积-BFS
//https://leetcode.cn/problems/max-area-of-island/submissions/
class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int m = grid.size(),n = grid[0].size();
        int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
        vector<vector<bool>> visit(m,vector<bool>(n,true));
        queue<pair<int,int>> pq;
        int ret = 0;
        for(int i = 0;i<m;++i)
            for(int k = 0;k<n;++k)
            {
                if(grid[i][k]==1 && visit[i][k])
                {
                    int area = 1;
                    pq.push({i,k});
                    visit[i][k]=false;
                    while(!pq.empty())
                    {
                        pair<int,int> tmp = pq.front();
                        pq.pop();
                        for(int j=0;j<4;++j)
                        {
                            int x=tmp.first+dx[j],y=tmp.second+dy[j];
                            if(x>=0&&x<m&&y>=0&&y<n&&visit[x][y]&&grid[x][y]==1)
                            {
                                pq.push({x,y});
                                visit[x][y]=false;
                                ++area;
                            }
                        }
                    }
                    ret = max(ret,area);
                }
            }
        return ret;
    }
};



//被围绕的区域-BFS
//https://leetcode.cn/problems/surrounded-regions/
class Solution {
    int m = 0, n = 0;
public:
    void solve(vector<vector<char>>& board) {
        m = board.size(), n = board[0].size();
        char mark = '.';
        //先把在边界的区域标记
        for (int i = 0; i < m; ++i) //扫描第一列和最后一列
        {
            if (board[i][0] == 'O') bfs(board, i, 0, mark);
            if (board[i][n - 1] == 'O') bfs(board, i, n - 1, mark);
        }
        for (int i = 0; i < n; ++i) //扫描第一行和最后一行
        {
            if (board[0][i] == 'O') bfs(board, 0, i, mark);
            if (board[m - 1][i] == 'O') bfs(board, m - 1, i, mark);
        }

        for (int i = 0; i < m; ++i)
            for (int k = 0; k < n; ++k)
                if (board[i][k] == 'O') board[i][k] = 'X';
                else if (board[i][k] == mark) board[i][k] = 'O';


    }

    //bfs遍历 将指定字符修改为tar
    void bfs(vector<vector<char>>& board, int x, int y, char revise)
    {
        int dx[] = { 0,0,1,-1 }, dy[] = { 1,-1,0,0 };
        char target = board[x][y];
        board[x][y] = revise;
        queue<pair<int, int>> pq;
        pq.push({ x,y });
        while (!pq.empty())
        {
            pair<int, int> tmp = pq.front();
            pq.pop();
            
            for (int i = 0; i < 4; ++i)
            {
                int px = tmp.first + dx[i], py = tmp.second + dy[i];
                if (px >= 0 && px < m && py >= 0 && py < n && board[px][py] == target)
                {
                    pq.push({ px,py });
                    board[px][py] = revise;
                }
            }
        }
    }
};



/* ======================================================= 最短路径问题 ======================================================= */

//迷宫中离入口最近的出口
//https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/submissions/
class Solution {
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int m = maze.size(), n = maze[0].size();
        vector<vector<bool>> visit(m, vector<bool>(n, true));
        int dx[] = { 0,0,1,-1 }, dy[] = { 1,-1,0,0 };
        queue<pair<int, int>> pq;
        pq.push({ entrance[0],entrance[1] });
        visit[entrance[0]][entrance[1]] = false;

        int count = 0; //记录层数
        //层数就能决定最短路径

        while (!pq.empty())
        {
            ++count;
            int sz = pq.size();
            while (sz--)
            {
                pair<int, int> tmp = pq.front();
                pq.pop();
                for (int i = 0; i < 4; ++i)
                {
                    int x = tmp.first + dx[i], y = tmp.second + dy[i];
                    if (x >= 0 && x < m && y >= 0 && y < n && visit[x][y] && maze[x][y] == '.')
                    {
                        if (x == m - 1 || y == n - 1 || x == 0 || y == 0) return count;
                        pq.push({ x,y });
                        maze[x][y] = false;
                    }
                }
            }
        }
        return -1;
    }
};



//最小基因变化
//https://leetcode.cn/problems/minimum-genetic-mutation/submissions/
class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        //如果不需要变化 则返回0
        if(startGene==endGene) return 0;
        //如果基因库中没有最终变化的序列 则无法找到
        if(find(bank.begin(),bank.end(),endGene) == bank.end()) return -1;

        unordered_set<string> visit; //判断这个基因序列是否已经判断过
        unordered_set<string> bk(bank.begin(),bank.end()); //将bank放入hash表方便查找

        const char* gene = "ACGT";

        queue<string> pq;
        pq.push(startGene);
        visit.insert(startGene);

        int ret = 0;
        //从startGene开始依次变化 一直变化到endGene为止
        while(!pq.empty())
        {
            ++ret; //每一层只会变化一个符
            //下一次遍历就是变化第二个字符
            int n = pq.size();
            while(n--)
            {
                //每个基因有八个字符 八个字符依次变化
                //如果变化了存在基因库中 就对下一个字符继续变化 变化一次 计数就+1
                for(int i = 0;i<8;++i) //每一个序列有八位
                {
                    string tmp = pq.front(); //我们一次只能变化一位
                    for(int k = 0;k<4;++k) //每一位可以变化四次(实际为三次)
                    {
                        tmp[i]=gene[k];
                        //如果该序列没有被查找过且在基因库中 则加入序列
                        if(tmp == endGene) return ret; //如果变化过后是目标则直接返回次数
                        if(!visit.count(tmp) && bk.count(tmp))
                        {
                            pq.push(tmp);
                            visit.insert(tmp);
                        }
                    }
                }
                pq.pop();
            }
        }
        return -1;
    }
}; 



//单词接龙
//https://leetcode.cn/problems/word-ladder/submissions/
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        if(find(wordList.begin(),wordList.end(),endWord)==wordList.end()) return 0;
        unordered_set<string> visit; //记录已经访问过的序列
        unordered_set<string> dict(wordList.begin(),wordList.end()); //记录词典方便查找
        int len = beginWord.size();
        queue<string> pq;
        pq.push(beginWord);
        visit.insert(beginWord);

        //初始ret为1 因为记录转换一共有多少个单词 beginWord 也算一个变换单词
        int ret = 1;
        while(!pq.empty())
        {
            ++ret;
            int n = pq.size();
            while(n--)
            {
                for(int i = 0;i<len;++i)
                {
                    string tmp = pq.front();
                    for(char k = 'a';k<='z';++k)
                    {
                        tmp[i]=k;
                        if(tmp==endWord) return ret;
                        if(!visit.count(tmp) && dict.count(tmp))
                        {
                            pq.push(tmp);
                            visit.insert(tmp);
                        }
                    }
                }
                pq.pop();
            }
        }
        return 0;
    }
};



//为高尔夫比赛砍树
//https://leetcode.cn/problems/cut-off-trees-for-golf-event/description/
class Solution {
    int m = 0, n = 0;
public:
    int cutOffTree(vector<vector<int>>& forest) {
        //存入每一个树的高度和下标
        vector<pair<int,int>> grid;
        m = forest.size(), n = forest[0].size();
        for (int i = 0; i < m; ++i)
            for (int k = 0; k < n; ++k)
                if (forest[i][k] > 1) grid.push_back({i,k}); //将有树的地方记录
        
        sort(grid.begin(), grid.end(), [&](const pair<int, int>& left, const pair<int, int>& right) {
            return forest[left.first][left.second] < forest[right.first][right.second];
        });


        int ret = 0;
        int path = 0;
        int x = 0, y = 0;
        for (const auto& val : grid) //每一个要找的坐标
        {
            path = bfs(forest, val.first, val.second, x, y);
            if (path == -1) return -1;
            ret += path;
            x = val.first, y = val.second;
        }
        return ret;
    }

    int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
    bool visit[51][51];
    int bfs(vector<vector<int>>& forest,int tarx,int tary,int startx,int starty)
    {
        if (tarx == startx && tary == starty) return 0;
        queue<pair<int, int>> pq;
        memset(visit,true,sizeof(visit));
        int step = 0;
        pq.push({ startx ,starty });
        visit[startx][starty] = false;
        while (!pq.empty())
        {
            ++step;
            int sz = pq.size();
            while (sz--)
            {
                auto tmp = pq.front();
                pq.pop();

                for (int i = 0; i < 4; ++i)
                {
                    int x = tmp.first + dx[i], y = tmp.second + dy[i];
                    if (x >= 0 && x < m && y >= 0 && y < n && visit[x][y] && forest[x][y])
                    {
                        if (x == tarx && y == tary) return step;
                        visit[x][y] = false;
                        pq.push({ x,y });
                    }
                }
            }
        }
        return -1;
    }
};



/* ======================================================= 多源BFS ======================================================= */

// 01矩阵
//https://leetcode.cn/problems/01-matrix/submissions/
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        //可以将为1的下标全部加入队列然后宽搜0 但是这样当我们找到为0的下标时却不知道起点
        //此时可以反过来将0添加到队列并将对应的dist数组值初始化为0 这样从0到为1的下标直接赋值步数即可
        int m = mat.size(),n = mat[0].size();
        vector<vector<int>> dist(m,vector<int>(n,-1));
        queue<pair<int,int>> pq;
        //将为0的下标加入队列并初始化dist数组值
        for(int i = 0;i<m;++i)
            for(int k = 0;k<n;++k)
            {
                if(mat[i][k]==0)
                {
                    pq.push({i,k});
                    dist[i][k]=0;
                }
            }

        int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
        while(!pq.empty())
        {
            pair<int,int> tmp = pq.front();
            pq.pop();
            for(int i = 0;i<4;++i)
            {
                int x=tmp.first+dx[i],y=tmp.second+dy[i];
                if(x>=0&&x<m&&y>=0&&y<n&&dist[x][y]==-1&&mat[x][y]==1)
                {
                    dist[x][y]=dist[tmp.first][tmp.second]+1;
                    pq.push({x,y});
                }
            }
        }
        return dist;
    }
};



//飞地的数量
//https://leetcode.cn/problems/number-of-enclaves/submissions/
class Solution {
public:
    int numEnclaves(vector<vector<int>>& grid) {
        int m = grid.size(),n = grid[0].size();
        vector<vector<int>> dist(m,vector<int>(n,0));

        //将边界中所有的1下标加入队列 遍历有多少边界上的1可以到达内部的1 内部没有被达到的1就是答案
        queue<pair<int,int>> pq;
        for(int i = 0;i<m;++i) //第一列和最后一列
        {
            if(grid[i][0]) pq.push({i,0}),dist[i][0]=1;
            if(grid[i][n-1]) pq.push({i,n-1}),dist[i][n-1]=1;
        }
        for(int i = 0;i<n;++i) //第一行和最后一行
        {
            if(grid[0][i]) pq.push({0,i}),dist[0][i]=1;
            if(grid[m-1][i]) pq.push({m-1,i}),dist[m-1][i]=1;
        }

        int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
        while(!pq.empty())
        {
            pair<int,int> tmp = pq.front();
            pq.pop();
            for(int i = 0;i<4;++i)
            {
                int x=tmp.first+dx[i],y=tmp.second+dy[i];
                if(x>=0&&x<m&&y>=0&&y<n&&dist[x][y]==0&&grid[x][y]==1)
                {
                    dist[x][y]=1;
                    pq.push({x,y});
                }
            }
        }

        int ret = 0;
        for(int i = 0;i<m;++i)
            for(int k = 0;k<n;++k)
                if(dist[i][k]==0&&grid[i][k]==1) ++ret; //统计有多少地方无法达到
        
        return ret;
    }
};



//地图中的最高点
//https://leetcode.cn/problems/map-of-highest-peak/submissions/
class Solution {
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        //从水域格子开始向往控制
        int m = isWater.size(),n = isWater[0].size();
        queue<pair<int,int>> pq;
        vector<vector<int>> ret(m,vector<int>(n,-1));

        for(int i = 0;i<m;++i)
            for(int k = 0;k<n;++k)
                if(isWater[i][k])
                {
                    ret[i][k] = 0;
                    pq.push({i,k});
                }

        int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
        while(!pq.empty())
        {
            const pair<int,int>& tmp = pq.front();
            for(int i = 0;i<4;++i)
            {
                int x=tmp.first+dx[i],y=tmp.second+dy[i];
                if(x>=0&&y>=0&&x<m&&y<n&&ret[x][y]==-1)
                {
                    ret[x][y] = ret[tmp.first][tmp.second]+1;
                    pq.push({x,y});
                }
            }
            pq.pop();
        }
        return ret;
    }
};



//地图分析
//https://leetcode.cn/problems/as-far-from-land-as-possible/submissions/
class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int m = grid.size(),n = grid[0].size();
        queue<pair<int,int>> pq;
        vector<vector<int>> dist(m,vector<int>(n,-1));

        for(int i = 0;i<m;++i)
            for(int k = 0;k<n;++k)
                if(grid[i][k])
                {
                    dist[i][k] = 0;
                    pq.push({i,k});
                }

        int ret = 0;
        int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
        while(!pq.empty())
        {
            const pair<int,int>& tmp = pq.front();
            for(int i = 0;i<4;++i)
            {
                int x=tmp.first+dx[i],y=tmp.second+dy[i];
                if(x>=0&&y>=0&&x<m&&y<n&&dist[x][y]==-1)
                {
                    dist[x][y] = dist[tmp.first][tmp.second]+1;
                    pq.push({x,y});
                    ret = max(dist[x][y],ret);
                }
            }
            pq.pop();
        }
        return ret==0?-1:ret;
    }
};





/* ======================================================= BFS与拓扑排序 =============================================================  */


//课程表
//https://leetcode.cn/problems/course-schedule/description/
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // prerequisites[1] -> prerequisites[0]
        unordered_map<int,vector<int>> hash; //邻接表 表示当前课程在那些课程学习之前(hash建邻接表)
        vector<int> in(numCourses); //记录入度 (在学习当前课程前需要学习的课程数量)

        for(vector<int>& v:prerequisites)
        {
            hash[v[1]].push_back(v[0]);
            ++in[v[0]];
        }

        queue<int> pq;
        for(int i = 0;i<numCourses;++i)
        {
            //将可以首先学习的课程加入队列(入度为0的节点)
            if(in[i] == 0) pq.push(i);
        }

        while(!pq.empty())
        {
            int& node = pq.front();
            for(int& x:hash[node]) //当前节点出队 将该课程下的其他课程入度-1
            {
                --in[x];
                if(in[x] == 0) pq.push(x); //如果该课程学习前的所有课程都学完了 就可以学习该课程了
            }
            pq.pop();
        }
        for(int i = 0;i<numCourses;++i) if(in[i]) return false;
        return true;
    }
};



//课程表II
//https://leetcode.cn/problems/course-schedule-ii/submissions/
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        // prerequisites[1] -> prerequisites[0]
        vector<vector<int>> hash(numCourses); //邻接表 表示当前课程在那些课程学习之前(二维数组建邻接表)
        vector<int> in(numCourses); //记录入度 (在学习当前课程前需要学习的课程数量)
        vector<int> ret;
        ret.reserve(numCourses);

        for(vector<int>& v:prerequisites)
        {
            hash[v[1]].push_back(v[0]);
            ++in[v[0]];
        }

        queue<int> pq;
        for(int i = 0;i<numCourses;++i)
        {
            //将可以首先学习的课程加入队列(入度为0的节点)
            if(in[i] == 0) pq.push(i);
        }

        while(!pq.empty())
        {
            int& node = pq.front();
            ret.push_back(node);
            for(int& x:hash[node]) //当前节点出队 将该课程下的其他课程入度-1
            {
                --in[x];
                if(in[x] == 0) pq.push(x); //如果该课程学习前的所有课程都学完了 就可以学习该课程了
            }
            pq.pop();
        }
        for(int i = 0;i<numCourses;++i) if(in[i]) return {};
        return ret;
    }
};



//火星词典
//https://leetcode.cn/problems/Jf1JuT/description/
class Solution {
public:
    string alienOrder(vector<string>& words) {
        int n = words.size();
        unordered_map<char, unordered_set<char>> hash; //建立邻接表
        unordered_map<char, int> in; //入度

        //初始化 图表
        for (int i = 0; i < n; ++i)
            for (char c : words[i]) in[c] = 0;

        //建图
        for (int i = 0; i < n; ++i)
        {
            for (int k = i + 1; k < n; ++k) //依次列举所有先后关系
            {
                int sz = min(words[i].size(), words[k].size());
                int j = 0;
                while (j < sz)
                {
                    if (words[i][j] != words[k][j])
                    {
                        if (!hash.count(words[i][j]) || !hash[words[i][j]].count(words[k][j]))
                        //words[i][j]没有被插入过 或 words[k][j]不在该列表里 才插入 防止重复
                        {
                            //第i个单词的该字母在第k个单词的该字母前面
                            hash[words[i][j]].insert(words[k][j]);
                            ++in[words[k][j]]; //这里可能会出现重复计数的情况
                        }
                        break;
                    }
                    ++j;
                }
                //这里如果第二个字符串遍历完了，第一个还没有遍历完 那么这个词是不合法的
                if (j == words[k].size() && j < words[i].size()) return "";
            }
        }

        //拓扑排序
        queue<char> pq;
        for (auto& s : in)
            if (s.second == 0) pq.push(s.first);

        string ret;
        while (!pq.empty())
        {
            char c = pq.front(); pq.pop();
            ret.push_back(c);
            for (auto& x : hash[c]) //去掉一个节点 该节点下的所有边也去掉
                if (--in[x] == 0) pq.push(x);
        }
        for (auto& pa : in) if (pa.second) return ""; //如果还有边没出 则存在环
        return ret;
    }
};


